%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi/2021/09.03.12.46
%2 sid.inpe.br/sibgrapi/2021/09.03.12.46.59
%@doi 10.1109/SIBGRAPI54419.2021.00014
%T Optimized 2D Ball Trees
%D 2021
%A Retondaro, Luis Carlos dos Santos Coutinho Retondaro,
%A Esperança, Claudio,
%@affiliation CEFET/RJ - Centro Federal de Educação Tecnológica do Rio de Janeiro
%@affiliation Programa de Engenharia de Sistemas e Computação COPPE - Universidade Federal do Rio de Janeiro
%E Paiva, Afonso ,
%E Menotti, David ,
%E Baranoski, Gladimir V. G. ,
%E Proença, Hugo Pedro ,
%E Junior, Antonio Lopes Apolinario ,
%E Papa, João Paulo ,
%E Pagliosa, Paulo ,
%E dos Santos, Thiago Oliveira ,
%E e Sá, Asla Medeiros ,
%E da Silveira, Thiago Lopes Trugillo ,
%E Brazil, Emilio Vital ,
%E Ponti, Moacir A. ,
%E Fernandes, Leandro A. F. ,
%E Avila, Sandra,
%B Conference on Graphics, Patterns and Images, 34 (SIBGRAPI)
%C Gramado, RS, Brazil (virtual)
%8 18-22 Oct. 2021
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K ball trees, spatial indexing, computational geometry.
%X Ball trees are hierarchical bounding structures -- usually binary trees -- where each node consists of a ball (circle, sphere, etc) enclosing its children. Approaches for building an optimal ball tree for a given set of leaves (points or balls enclosing other geometric primitives) typically rely on minimizing some function of the shape of the tree, regardless of the intended application. In this paper we examine the problem of building ball trees for 2D primitives, trying to balance construction time with the efficiency of the produced trees with respect to a set of distance-based queries. In particular, we present three new construction algorithms, propose an optimization whereby each internal node is the smallest ball enclosing all leaves rooted at that node, and describe enhancements to several distance query algorithms. Moreover, an extensive experimental study was conducted in order to evaluate our algorithms with different kinds of data sets, including ball collections that approximate 2D shapes.
%@language en
%3 34.pdf